#include <stdio.h>
#include <string.h>
#include <malloc.h>
#define NAMESIZE 20			//名称允许长度 
#define TRUE 1
#define FALSE 0
#define EqualFun strcmp
#define SetValue strcpy
typedef int STATUS;
typedef char NODE[NAMESIZE];//节点名称类型

struct NEIGHBORNODE
{
	NODE node;					//节点 
	struct NEIGHBORNODE *next;	//邻近节点 
};
typedef struct NEIGHBORNODE *NEIGHBOR;	//相邻节点类型
struct ANODE
{
	NODE node;					//节点 
	NEIGHBOR adjacents;			//邻近节点 
};
typedef struct ANODE ANYNODE;	//节点类型 
struct GRAPHNODE
{
	ANYNODE node;					//节点 
	struct GRAPHNODE *next;		//其他节点 
};
typedef struct GRAPHNODE *GRAPH;//图类型 
typedef struct NEIGHBORNODE *PATH;	//路径类型
struct PATHS
{
	PATH path;					//一条路径 
	struct PATHS *next;			//下一条路径
}; 
typedef struct PATHS *PATHS;		//路径集合类型
typedef struct PATHS *STACK;	//路径栈 


int Equal(NODE n1, NODE n2, int (*fun)()) 
{
    return (int)fun(n1, n2);
}

void Set(NODE n1, NODE n2, char *(fun)())
{
    fun(n1, n2);
}

NEIGHBOR AddANeighbor(NEIGHBOR nb, NODE node)  	
{//在nb节点群中增加一个相邻节点node
    NEIGHBOR b, pb;					//相邻节点变量 
    b = (NEIGHBOR)malloc(sizeof(struct NEIGHBORNODE));	//动态开辟一个相邻单元 
    b->next = NULL;
    Set(b->node, node, SetValue);					//本例中与strcpy(b->node, node);等价 
    if (nb == NULL)							//没有相邻节点的情况 
        nb = b;
    else									//有相邻节点的情况 
    {
        pb = nb;
        while (pb -> next) pb = pb -> next;
        pb -> next = b;
    }
    return nb;								//返回相邻节点 
}

GRAPH Form_Pa_Ch(NODE pa, NEIGHBOR nb) 
{//一个节点与其所有相邻节点
    GRAPH anynode;
    anynode = (GRAPH)malloc(sizeof(struct GRAPHNODE));//创建节点 
    Set(anynode->node.node, pa, SetValue);
    anynode->node.adjacents=nb;//相邻节点与节点成链 
    anynode->next=NULL;
    return anynode;								//返回节点
}

GRAPH AddAsubTree(GRAPH graph, GRAPH subgraph)	
{// 节点加入上一层节点
    GRAPH g = graph;			//临时(图),应该是链吧
    if(graph == NULL)		//图不存在 
        graph = subgraph;		//你懂得, 只有一个节点, 直接进
    else                    //图存在
    {
        while (g->next) g = g->next;
        g->next = subgraph;	//搞一个新的子链
    }
    return graph;			//返回图指针 
}

NEIGHBOR ClearAdjacents(NEIGHBOR nb)	
{//回收图节点空间 
    NEIGHBOR nb1 = nb;				//临时节点变量 
    while (nb)
    {
        nb1 = nb;
        nb = nb->next;
        free(nb1);					//回收单元 
    }
    return nb;						//返回NULL 
}

GRAPH ClearGraph(GRAPH graph)			//回收图节点相邻节点空间 
{
    GRAPH graph1 = graph;				//临时图
    while (graph)
    {
        graph1 = graph;
        graph = graph->next;
        free(graph1);				//回收单元 
    }
    return graph;					//返回NULL
}

void CreateStr(char *neighborset)	//字符数组转换为多个字符串 
{
    char *c = neighborset;				//临时字符串 
    while (*c)
    {
        if(*c == '/') *c = '\0';				//插入字符串结束标记 
        c++;
    }
    c++;
    *c = '\0';						//多一个结束标记 
}

NEIGHBOR CreateNeighbors(NEIGHBOR neighbors, char *neighborset)
{                                                   //若干个节点构成所有邻近节点
    char *p = neighborset;							//多个节点，分隔符'/' 
    NODE node;
    CreateStr(neighborset);							//变为多个字符串 
    while (*p)
    {//与strcpy(node, p);等价，读取节点 
        Set(node, p, SetValue);
        neighbors = AddANeighbor(neighbors, node);		//加入邻近关系中 
        p += strlen(node) + 1;
    }
    return neighbors;								//返回邻近节点链表 
}

GRAPH CreateGraph(GRAPH graph, char *filename)	//从文件创建图 
{
    GRAPH subgraph;
    NEIGHBOR neighbors;
    FILE *fp;
    char anynode[200], neighborset[5000];
    fp = fopen(filename, "r");
    while (!feof(fp))							//文件中是否还存在图的节点名称 
    {
        fscanf(fp, "%s", anynode);				//读入双亲节点 
        fscanf(fp, "%s", neighborset);
        neighbors = NULL;					//读入若干兄弟节点（子节点），分隔符'/' 
        neighbors = CreateNeighbors(neighbors, neighborset);		//构建双亲节点 
        subgraph = Form_Pa_Ch(anynode, neighbors);				//构建子树 
        graph = AddAsubTree(graph, subgraph);					//树中加入子树
    }
    fclose(fp);
    return graph; 
}

NEIGHBOR CopyAdjacents(NEIGHBOR adjacents)				//节点集复制 
{
    NEIGHBOR copynode, lastnode, head = NULL;			//没有子节点 
    while (adjacents)
    {
        copynode = (NEIGHBOR)malloc(sizeof(struct NEIGHBORNODE));
        Set(copynode->node, adjacents->node, SetValue);//复制节点 
        copynode->next = NULL;
        if(head == NULL) head = copynode;//第一个节点 
        else									//建立链接，复制子节点集 
            lastnode->next = copynode;
        lastnode = copynode;
        adjacents = adjacents -> next; 				//下一个节点 
    }
    return head;									//返回头节点指针 
}

NEIGHBOR ExpandNodes(GRAPH graph, NODE pa)		//由节点获取所有子节点
{
    NEIGHBOR adjacents = NULL;					//孩子节点 
    GRAPH g = graph;								//树 
    while (g)									//节点不为空 
    {
        if(Equal(g->node.node, pa, EqualFun)==0)
        {//找到分支节点 
        
            adjacents = CopyAdjacents(g->node.adjacents);
            break;
        }
        g = g->next;							//下一个双亲节点 
    }
    return adjacents;
}

// 路径求解新增内容
PATH AddANodeToPath(NODE node, PATH path)
{//节点加入路径中
    PATH p;
    p = (NEIGHBOR)malloc(sizeof(struct NEIGHBORNODE)); //开辟节点空间
    Set(p->node, node, SetValue);                    //赋值
    if(path == NULL)                                 //路径上第一个节点
        p->next = NULL;
    else
        p->next = path;                             //加入到路径头部
    path = p;                                       //路径倒序加入
    return path;                                    //返回路径头部
}

PATH CopyPath(PATH path)
{// 复制路径
    PATH tempath;
    tempath = (PATH)CopyAdjacents((NEIGHBOR)path);    //路径与兄弟节点集合相同
    return tempath;
}

struct PATHS *CopyPaths(struct PATHS *paths)
{// 复制路径集合, 返回路径集合的指针
    struct PATHS *copynode, *lastnode, *head = NULL;
    while (paths)                                       // 路径集合不为空
    {
        copynode = (struct PATHS*) malloc(sizeof(struct PATHS)); //路径节点
        copynode->path = CopyPath(paths->path);         // 复制一条路径
        copynode->next = NULL;                          // 复制路径
        if (head == NULL)                               // 第一条路径
            head = copynode;
        else                                            // 其他路径
            lastnode->next = copynode;
        lastnode = copynode;                            // 加入路径集合
        paths = paths->next;
    }
    return head;
}

void RevPath(PATH path)
{// 路径倒序
    int num = 0, i;
    NODE *nodes;
    PATH p = path;
    while (p)                                       //统计路径节点的个数
    {
        p = p->next;num++;        
    }
    nodes = (NODE *)malloc(num*sizeof(NODE));       // 开辟一维数组
    for(i = 0,p = path;p;p = p->next, i++)          //读取路径节点置于数组中
        Set(nodes[i], p->node, SetValue);           
    for(i = num - 1, p = path; p; p = p->next, i--)//数组数据倒序置于路径中
        Set(p->node, nodes[i], SetValue);          
    free(nodes);                                   //回收数组空间
}

void priAdjacents(NEIGHBOR adjacent)
{
	if(adjacent == NULL) return;
    while (adjacent->next)
    {
        printf("%s,",adjacent->node);
        adjacent = adjacent->next;
    }
    printf("%s",adjacent->node);
}

void priPath(PATH path)
{//显示路径, 复用了显示兄弟函数  
    priAdjacents((NEIGHBOR)path);                     // 路径与兄弟节点集合形式相同
}

struct PATHS* AddAPathToPaths(PATH path, struct PATHS* paths)
{//路径加入路径集合
    PATH copypath;
    struct  PATHS *ps = NULL, *p;
    if(path == NULL) return paths;                  // 没有路径
    copypath = CopyPath(path);                      // 复制路径
    ps = (struct PATHS *)malloc(sizeof(struct PATHS)); // 开辟路径集合节点
    ps->path = copypath;                               // 复制的路径置入
    ps->next = NULL;                                
    if (paths == NULL)                              // 路径集合为空
        paths = ps;                        
    else                                            // 新节点路径放置最后
    {
        p = paths;
        while(p->next) p = p->next;
        p->next = ps;
    }
    return paths;    
}

PATH ClearPath(PATH path)
{// 回收路径空间
    path = (PATH)ClearAdjacents((NEIGHBOR)path); // 路径与兄弟节点集合形式相同
    return path;
}

struct PATHS* ClearPaths(struct PATHS* paths)
{// 回收路径空间
    struct PATHS *paths1 = paths;
    while(paths)                              // 所有路径
    {
        paths1 = paths;
        ClearPath(paths1->path);             //回收一条路径空间
        paths = paths->next;                 // 下一条路径
        free(paths1);
    }
    return paths;
}

STACK PushAPath(STACK stack, PATH path)
{// 一条路径进栈
    PATH tempath;
    STACK st;
    tempath = CopyPath(path);                           // 复制路径
    st = (struct PATHS*)malloc(sizeof(struct PATHS));   // 路径节点
    st->path = tempath;                                 // 置路径于栈中
    if (stack == NULL)                                  // 第 1 条路径
        st->next = NULL;
    else                                                // 已有路径
        st->next = stack;
    stack = st;
    return stack;
}

STACK PushPaths(STACK stack, struct PATHS *paths)
{// 所有路径进栈
    struct PATHS *p, *head;
    head = CopyPaths(paths);                // 复制路径集合
    p = head;
    if(p != NULL)                           // 逐一加入栈中
    {
        while(p->next) p = p->next;
        p->next = stack;
        stack = head;
    }
    return stack;
}

STACK PopANode(STACK stack, NODE node, PATH *path)
{
    STACK p = stack;
    PATH tempath;
    if(p != NULL)
    {  
        tempath = p->path;                              // 一条路径
        Set(node, tempath->node, SetValue);             // 获取节点
        *path = CopyPath(tempath);                      // 获取路径
        stack = p->next;                                // 栈顶变化
        free(p);                                        // 删除路径
    }
    return stack;                                       // 返回栈顶
}

STACK ClearStack(STACK stack)
{// 回收栈空间
    stack = ClearPaths((struct PATHS *)stack);          //堆栈与路径集合的形式相同
    return stack;
}

STATUS IsInPath(NODE node, PATH path)			//节点在路径中 
{
	PATH p=path;
	STATUS flag=FALSE;
	while(p)									//节点是否在路径中的标识 
	{
		if(Equal(node, p->node, EqualFun)==0)	//node在路径中 
		{
			flag=TRUE;
			break;	
		}
		else
			p=p->next;
	}
	return flag;								//返回真、假值 
}

NEIGHBOR DeleteNodeInPath(NEIGHBOR adjacents, PATH path)
{									//从adjacents中删除节点在路径path中的节点 
	NEIGHBOR n1=adjacents, n2;		
	STATUS flag=FALSE;
	while(n1)							//节点集合的每个节点 
	{							
		flag=IsInPath(n1->node, path);	//节点是否在路径中 
		if(flag==TRUE)					//节点在路径中 
		{
			if(n1==adjacents)			//删除节点 
			{
				adjacents=n1->next;		//下一个节点 
				free(n1);				//删除当前节点 
				n1=adjacents;			//其他节点 
			}
			else						//删除节点 
			{
				n2->next=n1->next;		//NULL 
				free(n1);				//删除当前节点 
				n1=n2->next;			//NULL 
			}
		}
		else							//节点不在路径中 
		{
			n2=n1;						//下一个节点 
			n1=n1->next;
		}
	}
	return adjacents;
}

PATHS FormPathsFromNodes(NEIGHBOR adjacents, PATH path, PATHS paths)
{						//将不在路径中的节点加入路径，形成路径集合 
	PATH tempath;
	adjacents=DeleteNodeInPath(adjacents, path);			//删除构成回路的节点 
	while(adjacents)										//所有不构成回路的节点 
	{
		tempath=CopyPath(path);								//复制路径 
		tempath=AddANodeToPath(adjacents->node, tempath);	//路径中加入一个节点 
		paths=AddAPathToPaths(tempath, paths);				//新路径加入路径集合 
		adjacents=adjacents->next;							//下一个节点 
	}	
	return paths;											//下一个路径集合 
}

STATUS SearchPath(GRAPH graph, NODE start, NODE end, PATH *path)
{//判断节点是否在图中，并获取路径 
	NODE node;
	NEIGHBOR adjacents;
	STACK stack=NULL;
	STATUS flag=FALSE;
	PATH tempath=NULL;
	struct PATHS *paths=NULL;
	if(graph==NULL) return flag;//没有图
	tempath=AddANodeToPath(start, tempath);		//初始节点形成路径 
	stack=PushAPath(stack, tempath);			//路径进栈 
	while(stack)								//任意一条路径 
	{
		tempath=ClearPath(tempath);				//清空路径 
		stack=PopANode(stack, node, &tempath);	//出栈 
		if(Equal(end, node, EqualFun)==0)		//目标节点 
		{
			flag=TRUE;							//找到目标节点 
			*path=CopyPath(tempath);			//获取路径 
			break;
		}
		adjacents=ExpandNodes(graph, node);		//相邻所有节点 
		paths=FormPathsFromNodes(adjacents, tempath, paths);
												//形成不带回路的路径集合 
		stack=PushPaths(stack, paths);			//所有路径进栈 
		paths=ClearPaths(paths);				//回收所有路径 
	 } 
	 ClearStack(stack);							//清除堆栈 
	 return flag;
}

void main(int argc, char const *argv[])
{//测试求解路径
    printf("\n==================\n");
	NODE start, end;					//起始节点 
	PATH path=NULL;						//	路径 
	STATUS flag;						//节点是否在图中 
	GRAPH graph=NULL;					//图 
	char *filename="graph.txt";			//图文件 
	graph=CreateGraph(graph, filename);	//建立图存储结构 
	printf("The Start Node:");			 
	scanf("%s", start);					//输入任一起点节点名 
	printf("The End Node:");
	scanf("%s", end);					//输入任一终点目标名 
	flag=SearchPath(graph, start, end, &path);	 //节点start到end的路径 
	printf("Search %s from %s, Status=%d\n", end, start, flag);	//显示状态 
	if(flag != 0) printf("Path=");
	RevPath(path);						//路径倒序 
	priPath(path);						//显示路径 
	printf("\n==================\n");
	ClearGraph(graph);					//清空图存储单元 
}
